package dp.base;

import org.apache.commons.math3.util.MathUtils;

public class CoinCharge {
    /**
     * 暴力递归，它是一个自顶向下的调用，什么叫做自定向下，可以理解为较大的数，不断地
     * 调用较小的数，较小的数又调用其它更小的数，这个就叫做一个自顶向下的一个调用过程
     * 暴力递归就是一个自顶向下的一个调用过程，它的问题是出现了重叠子问题
     * <p>
     * 什么叫做重叠子问题:问题的规模最开始为n,接下来调用coins(n-5),coins(n-1)...,它
     * 的规模就变小了,想当于大问题在调用它的子问题。我们下面的四个都算是n的子问题。
     * <p>
     * 而且这些子问题是有重复的，也就是很多的子问题进行了重复的计算。出现了重叠子问题的时候
     * 我们会想到一个解决的方法就算记忆化搜索，什么叫做记忆化搜索呢？看下面的另一个方法
     */

    /**每一次选择硬币都有四种选择，我们要选择里面dp(n)最小的，然后 dp(n) = dp(n-k) + 1
     * 所以现在需要通过三个Math.min选择出四个选择中次数最小的，每一次选择出最小后需要+1，也就是dp(n)=dp(n-k)+1。
     * 需要注意的是如果硬币等于 25分 or 20分 or 5分 or 1分的时候，直接return 1就行
     * 因为上面的这四种情况出现时，只需要一枚硬币，这个是递归的终止条件。
     * 需要注意的是，如果硬币是19等特殊数字的时候，n-20会产生一个负数。所以为了使得产生负数直接取消比较资格，
     * 我们需要另一个边界条件。就是如果传入的n小于0直接return一个特别大的数就行，也就是直接return Integer.MAX_VALUE
     *
     * 下面这个代码存在的问题，下面的这个代码其实是一个递归的写法，它的复杂度是2^n
     * 它的调用和斐波那契数列的调用方式很像
     * int fib(int n){
     *      if(n<=2) return 1;
     *      return fib(n-1)+f(n-2);
     * }
     * 它里面存在一些重复的计算的调用，斐波那契额数列也存在大量重复的计算
     * 比如我们要求5
     *     fib(5) = fib(4)+fb(3)=fib(3)+fib(2)+fib(2)+f(1)=
     *     f(2)+f(1)+f(2)+f(2)+f(1)=5
     *
     *     f(4) = fib(3)+f(2)=fib(2)+fib(1)+fib(2)=3
     *
     *     f(10) = f(9)+f(8)=f(8)+f(7)+f(7)+f(6)=f(7)+f(6)+f(6)+f(5)+f(6)+f(5)+f(5)+f(4)=
     *     f(6)+f(5)+f(5)+f(4)+f(5)+f(4)+f(5)+f(5)+f(4)+f(5)+f(5)+f(4)=
     *     f(5)+f(4)+f(5)+f(5)+f(4)+f(5)+f(4)+f(5)+f(5)+f(4)+f(5)+f(5)+f(4)=40+15=55
     *而我们的这个找硬币的方法同样也存在大量重复的计算
     *     假设我们现在传入的n是6，也就是coins(6)
     *     coins(6)->coins(5)+coins(1)->coins(0)+coins(4)+coins(1)->coins(1)->coins(0)
     *     如果n的传入的数字非常大，它存在很多重复的情况。
     *
     * 因为暴力递归存在很多重复的情况，我们现在要考虑如何去优化它呢。
     * 我们刚一开始想使用动态规划，一上来就会想到暴力递归，下面的方法就算暴力递归
     * 时间复杂度是指数级，4的n次幂
     */
    static int coins1(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;

        int min1 = Math.min(coins1(n - 25), coins1(n - 20));
        int min2 = Math.min(coins1(n - 5), coins1(n - 1));

        // 从（n - x）这4个选择里选出最小的之后要加上减去的那个分
        return Math.min(min1, min2) + 1;
    }

    static int fib(int n) {
        if (n <= 2) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 记忆化搜索(自顶向下的调用)
     * 记忆化搜索就是把曾经算过的那个值，曾经求解过的那个子问题的解给存起来，这个就叫做记忆化
     * 其实它就是缓存，我们可以考虑使用数组来解决这个事情。所谓记忆化就是把出现了的值放到内存
     * 里面去
     * <p>
     * 我们应该如何去实现呢？我们先要引入一个数组，因为是动态思想，这个数组，一般我们把它命名
     * dp,问题是这个数组是干嘛用的，这个数组的作用是:假如我们调用了coins(6),它算出来的值是凑
     * 齐6分至少要花费最少硬币的个数是多少。一旦我们算出来的值是4枚硬币，这个时候我们就会把
     * dp[16]赋值为4。所以dp数组的意思是，如果是dp[16]就代表要凑够16分的话，它所需的最下硬币
     * 个数我们把它存起来。就是这么一个道理。
     * dp[n]就是凑够n分需要的最小硬币个数。为了能够直接dp[n]所以我们在给这个数组申请内存的时候
     * 传入的长度是n+1,因为数组的索引是从0开始的。 长度只有是n+1，才能够直接放n
     * <p>
     * 这个方法还是存在递归调用，但是每一个dp[n]=只会进入一次递归，有了值就不会再次进行递归取值
     * 操作。
     * <p>
     * 记忆化搜索依然是自定向下调用，还是一个较大的值调用一个较小的值。但是性能相比暴力搜索有较大的
     * 提升。
     */

    static int coins2(int n) {
        if (n < 1) return -1;
        /*
         * 因为传入n时如果n为19这样的特殊元素，可能会出现19-25=-6这样的数据，我
         * 们可以进一步对其进行做处理
         */
        int[] dp = new int[n + 1];

        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }

        return coins2(n, dp);
    }

    static int coins2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;

//        if (n == 1 || n == 5 || n == 20 || n == 25) {//初始化操作
//            dp[n] = 1;
//        }

        if (dp[n] == 0) {
            int min1 = Math.min(coins2(n - 25, dp), coins2(n - 20, dp));
            int min2 = Math.min(coins2(n - 5, dp), coins2(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        } else {
            return dp[n];
        }
        return dp[n];
    }

    /**
     * 上面了做了记忆化搜索，动态规划的最后一步叫做递推。我们只有写到递推这一步才能叫做
     * 真正的动态规划，递推和前面的暴力递归和记忆化搜索都是不一样的，它是自底向上的。前
     * 面的两步仅仅是前奏，我们刚开始发现能够暴力递归，然后我们发现能够使用记忆化搜索来
     * 优化，但是使用了记忆化搜索优化之后，发现还可以优化，那就算什么优化呢？就是递推。
     * 通过递推的形式，递推说的广泛一点，就是大家认为的非递归，也就是递推，当然有人也把递推
     * 叫做迭代，但是这里叫做递推比较好。就是一步一步的往前面推。
     */

    /**
     * 递推(自底向上)
     * 我们发现前面记忆化搜索的时候，定义了一个dp数组，用于记录搜索过的值。
     * 比如我们计算完了凑够n分最少要凑够多少枚硬币计算出来了，这个时候我们
     * 就将这个数放在这个数组里面去，dp(n)=凑足n分需要的最少的硬币数目。
     * 我们前面是由大到小的调用，从41到往下掉 16 21 26 40 然后这四个
     * 数字右会分成4个叉往下掉，一直往下，得到的dp[n]的值是先把d(n-25)的值
     * dp(n-20),dp(n-5),dp(n-1)的值算出来。只有将这四个值都算出来了，最终
     * 才能知道这个n的值是多少
     * 说白了，现在我们要求凑够41分的硬币个数，要先求出凑够16的硬币最小个数
     * 凑够21分的硬币最小个数，凑够36分和凑够40分的最小硬币个数。也就是我们要凑够比较
     * 大的硬币的分数，必然要先求出凑够哪些比较小的分需要的硬币个数。小的算出来了，才有办法
     * 求出比较大的，所以我们完全有理由相信我们可以由小算到大，因为本来这个式子就可以看得出来
     * 肯定要先算出小的。才能算出这个n比较大的
     * 所以我们这个dp[]这个数组完全可以由小往大的方向去算。我们通过下面的for循环来测试看
     * 这个结果能不能行，for(int i = 1; i <= n; i++){ dp[i] = ;}我们可以先求dp[1]一直到
     * dp[n]就可以了。这样就是由小到大的去算。那么我们的方法的返回值应该写啥呢？这个方法我们直接
     * 返回一个dp[n]就行了。问题是dp[i]我们要咋求呢？
     * 我们知道求dp[i]我们肯定是在dp[i-25],dp[i-20],dp[i-5],dp[i-1]中最小的值拿出来再
     * 加1，也就是反着通过不断地i+1、i+5,i+20,i+25来达到i+k=n 问题是我们的i是从1开始的，1-25，
     * 1-20...这些数据肯定是不合理的，i等于1的时候1-1好像也没有什么意义。这个时候我们就得去判断，
     * 首先来一个int min = Integer.MAX_VALUE; 然后去判断哪一个合适，也就是现在我们就直接通过比较直接获取最大得值，
     * 因为19-25小于0会导致索引越界。所以我们需要在前面加上一个越界判断条件
     */
    static int coins3(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
//            int min = Integer.MAX_VALUE;
//            if (i >= 1) min = Math.min(dp[i - 1], min);
            int min = dp[i - 1];
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[n];
    }
    /**
     * 为啥这个叫做动态规划？它的具体含义是啥，我们先不去了解先通过做题去领悟。
     * 我们需要知道的是，我们现在不断地给代码做优化，现在上面代码的时间复杂度是o(n)
     */

    /**
     * 思考题:请输出找零钱的具体方案(最少硬币，具体是使用了哪些面值的硬币)
     * 我们应该怎么做呢？我们现在用递推代码来进行实现。
     * 我们现在要凑够n分，它具体使用哪些面值。
     * <p>
     * 为了充分理解，我们还是先写成前面的代码，
     * if (n < 1) return -1;
     * int[] dp = new int[n + 1];
     * for (int i = 1; i <= n; i++) {
     * int min = Integer.MAX_VALUE;
     * if (i >= 1) min = Math.min(dp[i - 1], min);
     * if (i >= 5) min = Math.min(dp[i - 5], min);
     * if (i >= 20) min = Math.min(dp[i - 20], min);
     * if (i >= 25) min = Math.min(dp[i - 25], min);
     * dp[i] = min + 1;
     * }
     * return dp[n];
     * 首先我们dp[i]是指的凑够i分钱，最少需要多少枚硬币。所以我们就先考虑
     * 凑够i-1,i-5,i-20,i-25看一下凑够这些分数，哪一个硬币数是最小的
     * 把它们最小的值挑出来然后+1，这个1就是指的是最后一次选择了一枚硬币，它
     * 可能是1分、5分、20分、25分。
     * 我们的关键点就是在进入了那个if判断就可以知道它最后一次选择了哪一枚，
     * 举个例子，我们首先得搞清楚，min这个东西肯定是这四个当中的最小值。如果
     * 我们这一轮比较中发现dp[i-1],dp[i-5],dp[i-20],dp[i-25]中dp[i-20]是
     * 最小的，它是这四个当中最小的，那毫无疑问这个min就算dp[i-20],这就意味着
     * 你这一次选择了一枚20分的，也就是最后一次选择了一枚20分。意味着这一次min+1这个1代表，选择了一枚20分的硬币。
     * 只有我们这次选的是20,才会去使用dp[i-20]这个值,所以答案就出来了，我们要
     * 想知道这一次选择了那一枚，我们只需要看一下这个min它来自于那个if判断，如果我们
     * 这个min来自于if (i >= 20) min = Math.min(dp[i - 20], min),也就是一枚20分的，
     * 如果min来自于if (i >= 25) min = Math.min(dp[i - 25], min)说明选择的是一枚25分的，我们可以去记录一下。
     *
     * 应该如何去记录呢？因为我们这里是一个for循环，肯定是选择了很多次，所以我们可以考虑这么做，
     *      int[] faces = new int[dp.length];
     * 这个faces[i]是什么意思呢？它的意思代表+1选择了哪一枚，比如假如我们的min是选择
     * 的dp[i-20],说白了这一次的加1,代表选择了20分的，才会去考虑i-20凑够i-20需要多少硬币
     * 所以这一次选20的话，这个faces[i]=20，它存下来有啥作用呢？我们可以充分利用这个东西了，
     * 我们现在改写一下原来的代码
     * for(int i=1; i <= n;i++){
     * if(n<1) return -1;
     * int[] dp = new int[n+1];
     * int[] faces = new int[dp.length];
     * for(int i=1;i <= n;i++){
     * int min = Integer.MAX_VALUE;
     * if(i >= 1 && dp[i-1] < min){
     * min = dp[i-1];
     * faces[i] = 1;
     * }
     * if(i >= 5 && dp[i-5] < min){
     * min = dp[i-5];
     * faces[i] = 5;
     * }
     * if(i >= 20 && dp[i-20] <min){
     * min = dp[i-20];
     * faces[i] = 20;
     * }
     * if(i >= 25 && dp[i-25] <min){
     * min = dp[i-25];
     * faces[i] = 25;
     * }
     * }
     * }
     * 改写后的代码，最开始min=Integer.MAX_VALUE。当我们如果发现这个时候i >= 1的
     * 并且dp[i-1]又是比这个min小,说白了我们发现一个更小的值。所以我们应该把这个值给存起来
     * 一旦最小值使用了这个方案，也就是说，这一次，我们是选择了一枚一分的，如果i >= 5而且比
     * dp[i-5] < min，也就是min小于刚刚算的那个最小值还要小，那说明现在发现的最小值min = dp[i-5],
     * 如果我们这一次使用的最小值使用的是dp[i-5]说明这一次要选择必然是5分的。我们现在已经求完
     * 前面的，现在我们又发现i>=20，并且dp[i-20]<min,那么我们就让最小值是min=dp[i-20],一旦
     * 我们采取的是让min作为我们的最小值，意味着我们最后一次一定是选择的一枚20分的硬币。依次类推
     * 如果我们发现dp[i-25]还要更小，我们最小值就采取它，说白了这一次选择的硬币必然是25分的。我们
     * 才会考虑i-25分的最小值是多少。
     *
     * 理解这个问题的关键就在faces[i]的存储，这个答案就求存来了，这样我们就能够知道每一次
     * 拿到的硬币数是谁。求出这个东西之后有啥用，肯定是利用这个faces[]数组去搞事情
     */
    static int coins4(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        int[] faces = new int[dp.length];

        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            if (i >= 1 && dp[i - 1] < min) {
                min = dp[i - 1];
                faces[i] = 1;
            }
            if (i >= 5 && dp[i - 5] < min) {
                min = dp[i - 5];
                faces[i] = 5;
            }
            if (i >= 20 && dp[i - 20] < min) {
                min = dp[i - 20];
                faces[i] = 20;
            }
            if (i >= 25 && dp[i - 25] < min) {
                min = dp[i - 25];
                faces[i] = 25;
            }
            dp[i] = min + 1;
            print(faces, i, dp);
        }
//        print(faces,n);
        return dp[n];
    }

    private static void print(int[] faces, int n, int[] dp) {
        System.out.println("凑齐" + n + "分至少需要" + dp[n] + "硬币");
        while (n > 0) {
            System.out.println("需要" + faces[n] + "分1枚");
            n -= faces[n];
        }
    }

    /**
     * 这里我们没有具体了解啥是动态规划，只是先理解啥是暴力递归，记忆化搜索，递推，
     * 最后我们打印了一下这个具体的面值组成。
     * <p>
     * 下面我们需要给这个找零钱写一个通用的实现，就是可以由别人传面值进来，我们之前
     * 的面值都是固定死了的，我们可以搞一个由别人传面值进来，所以这里可以咋做呢？
     */
    static int coins5(int n, int[] faces) {
        if(n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if(i < face || dp[i - face] < 0) {
                    continue;
                }
                min = Math.min(dp[i - face], min);
            }
            if(min == Integer.MAX_VALUE){
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {

        System.out.println(coins5(41, new int[]{1, 5, 20, 25}));
    }
}

